package Prac;

public class P11_30 {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return buildTreeHelper(preorder,inorder,0,preorder.length-1);
    }



    /**
     * 利用前序遍历和中序遍历构建二叉树
     * [left,right]区间内构建树并返回根节点
     * @param preorder
     * @param inorder
     * @param left
     * @param right
     * @return
     */
    int index;
    private TreeNode buildTreeHelper(int[] preorder, int[] inorder, int left, int right) {
        if(left>right){
            //区间为空
            return null;
        }
        if(index==preorder.length){
            //前序遍历已遍历完全
            return null;
        }
        int rootVal = preorder[index];
        TreeNode root = new TreeNode(rootVal);
        index++;
        int pos = find(inorder,rootVal);
        root.left = buildTreeHelper(preorder,inorder,left,pos-1);
        root.right = buildTreeHelper(preorder,inorder,pos+1,right);
        return root;
    }

    private int find(int[] inorder, int key) {
        for (int i = 0; i <inorder.length ; i++) {
            if(inorder[i]==key){
                return i;
            }
        }
        return -1;
    }

}
